(1) Field of Invention
The present invention relates to a system for automatically identifying communities in networks and, more particularly, to a system for automatically identifying communities in networks based on relationships between connected vertices in the network.
(2) Description of Related Art
Community detection in networks has received significant attention in the previous decade, with hundreds of approaches being proposed (see the List of Cited Literature References, Literature Reference No. 3). Nearly all of these approaches operate on networks with undirected edges and no edge weights. While some methods have been proposed for directed, bipartite, or weighted networks, only recently has community detection been suggested for multigraphs, or multiplex networks.
Greene and Cunningham (see Literature Reference No. 4) proposed a method based on clustering the different modes of a multigraph separately and then combining them later to obtain the final community solution. Their framework is independent of the algorithm used to partition each mode of the network, with K-means being suggested as a first approximation. The clustering outputs of each mode are then unified through an ensemble method that uses agglomerative clustering over the community memberships. Because this method analyzes each network mode independently, it is unable to recognize regularities between modes, or higher-order relationships between the modes themselves. Furthermore, the method is unable to include information about the different modes and whether regularities between specific modes should be heavily weighted or ignored.
Mucha et al. (see Literature Reference No. 6) used Laplacian dynamics over a tensor to discover regularities in the different modes of a multigraph. Their tensor-based approach was generalized to time-dependent networks where each mode corresponds to a discrete time step, and to multiscale views of the same community. An analysis on a 3-mode social network showed how the Laplacian dynamics could be used to merge the independent community solutions. However, this method requires manual specification for a parameter that adjusts how the different modes are used. Furthermore, it cannot receive a priori information on the relationships between the different modes.
Selee et al. (see Literature Reference No. 8) proposed a tensor decomposition approach to community detection that clusters the decomposed structure of the tensor to identify communities. However, this approach does not supply a specific mechanism for discovering how many communities are present; it must be specified by the user. Furthermore, the scalability of the approach is limited by the high computational expense of the tensor decomposition.
Rodriguez and Shinavier (see Literature Reference No. 7) proposed a method for mapping multi-modal networks to single-mode networks so that community detection can be perform using existing algorithms. They use a network path-based algebra to decide which paths in the different modes should be present in the resulting single-mode network. This approach is unable to provide a complete community detection solution and requires that the resulting single-mode network discover communities that are consistent with the single-node projection of the multi-modal information.
Each of the prior methods described above exhibit limitations that make them incomplete. Thus, a continuing need exists for a system and method that enables community detection in multigraphs.